#ifndef ZL_ALGORITHM
#define ZL_ALGORITHM
#include "../Basic/String.h"
#include <vector>

namespace zl
{
	namespace algorithm
	{
		namespace trietree
		{
			template<typename T>
			class Edge;
			template<typename T>
			class TrieNode;

			template<typename T>
			class Edge
			{
			public:
				char                  value;
				TrieNode<T>*          source;
				TrieNode<T>*          target;
			};

			template <typename T>
			class TrieNode
			{
			public:
				std::basic_string<T,std::char_traits<T>,std::allocator<T>>   value;
				int                          freq;
				bool                         isword;
				std::vector<Edge<T>*>        edges;
			};

			template <typename T>
			class TrieTree
			{
			private:
				TrieNode<T>*                    root;
				Edge<T>*                        Find(TrieNode<T>* current, char c)
				{
					std::vector<Edge<T>*> edges = current->edges;
					for (auto i : edges)
					{
						if (i->value == c) return i;
					}
					return nullptr;
				}
				TrieNode<T>*                    NewNode(std::basic_string<T, std::char_traits<T>, std::allocator<T>> value, bool isword = false)
				{
					TrieNode<T>* node = new TrieNode<T>;
					node->value = value;
					node->freq = 1;
					node->isword = isword;
					return node;
				}
				Edge<T>*                        NewEdge(TrieNode<T>* source, TrieNode<T>* target, T c)
				{
					Edge<T>* edge = new Edge<T>;
					edge->source = source;
					edge->target = target;
					edge->value = c;
					return edge;
				}
				void                            Destory(TrieNode<T>* root)
				{
					for (auto ptr : root->edges)
					{
						Destory(ptr->target);
						delete ptr;
						ptr = nullptr;
					}
					delete root;
					root = nullptr;
				}
				void                          Search(TrieNode<T>* node, std::vector<std::basic_string<T, std::char_traits<T>, std::allocator<T>>>& res)
				{
					if (node->isword) res.push_back(node->value);
					for (auto edge : node->edges)
					{
						node = edge->target;
						Search(node, res);
					}
				}
			public:
				TrieTree()
				{
					root = new TrieNode<T>;
					root->value = "";
					root->isword = false;
					root->freq = 0;
				}

				~TrieTree()
				{
					Destory(root);
				}

				void              Add(std::basic_string<T, std::char_traits<T>, std::allocator<T>> word)
				{
					TrieNode<T>*  pcurrent = root;
					for (std::basic_string<T, std::char_traits<T>, std::allocator<T>>::size_type i = 0; i < word.length(); i++)
					{
						Edge<T>* edge = Find(pcurrent, word[i]);
						if (edge == nullptr)
						{
							TrieNode<T>* target = NewNode(word.substr(0, i + 1));
							Edge<T>* edge = NewEdge(pcurrent, target, word[i]);
							pcurrent->edges.push_back(edge);
							pcurrent = pcurrent->edges[pcurrent->edges.size() - 1]->target;
						}
						else
						{
							pcurrent = edge->target;
							pcurrent->freq++;
						}
					}
					pcurrent->isword = true;
				}

				std::vector<std::basic_string<T, std::char_traits<T>, std::allocator<T>>>        Search(std::basic_string<T, std::char_traits<T>, std::allocator<T>> key)
				{
					TrieNode<T>* pcurrent = root;
					std::vector<std::basic_string<T, std::char_traits<T>, std::allocator<T>>>  res;
					for (auto c : key)
					{
						Edge<T>* edge = Find(pcurrent, c);
						if (edge == nullptr) break;
						pcurrent = edge->target;
					}
					if (pcurrent != nullptr)
					{
						Search(pcurrent, res);
					}
					return res;
				}
			};

			typedef TrieTree<char>           ATrieTree;
			typedef TrieTree<wchar_t>        WTrieTree;
		};
	};
};

#endif